This invention relates to machine vision, and particularly to methods and apparatuses for feature detection.
Many machine vision applications use geometrical descriptions as canonical models for inspecting or aligning an object within an image. A geometrical description is a collection of data that specifies the basic geometry of the object, that is the location of object features and dimensions of the object features relative to each other, where the object features might include the object body, number of balls in a ball grid array, and the presence or absence of balls in a ball grid array, for example. A ball grid array is a surface-mount device consisting of a more-or-less rectangular package and a grid of balls. A geometrical-based model for a ball grid array typically consists of a grid spacing in two dimensions (x and y); a nominal, a minimum, and a maximum dimension of the balls in the grid; the presence or absence of balls at each of the grid points; and an origin location.
The machine-vision system can use a geometrical model to locate an instance of an object in an image and align the object in the proper orientation (i.e., register the object). Often, one or more balls are purposely missing to indicate the correct orientation of the ball grid array. For example, a vision-based automatic surface mounter (SMD) machine typically employs a geometrical-based model of a ball grid array to place the ball grid array on a printed circuit board by aligning, in the proper orientation, the balls with pads on the printed circuit board.
The process of creating accurate geometrical models of objects, either by manually measuring the dimensions of the object, or by extracting the dimensions from manufacturing specifications, can be very tedious, especially when the objects are complicated.
In many ball grid array applications, further problems exist because it is difficult to identify the balls in images because of lighting effects. The balls often image poorly because the metal balls specularly reflect the light of the imaging system, and, thus, image less accurately. Also, the three-dimensional shape of the balls causes shadowing, which obscures the balls in the images. The three-dimensional shape also causes stronger reflections from some portions of the balls more than from other portions. Additionally, cheaper light and optic systems or light and optic systems that are focused to image an aspect of the production other than identifying balls decrease the quality of the ball images. Each of these lighting effects contributes to poor quality ball images and often frustrates identification of the balls in images.
Several known machine-vision techniques are used to identify balls. One technique uses search tools, such as normalized correlation with a synthetic circular model, where normalized correlation searching is known in the art and described at B. K. D. Horn, xe2x80x9cRobot Visionxe2x80x9d, MIT Press, London England, 1985, Section 6.1.2, pp. 129-132. This technique often misses balls because of lighting effects. For example, FIG. 1 illustrates an instance of the reflectivity of a ball 100 against a background 108. The reflected light from the ball 100 forms two distinct regions, a brighter region, region 102, and a darker region, region 104. The search tool is searching the image for a match to the synthetic circular model. No single region 102, 104, or 108 is circular because of the lighting effects. Therefore, no single region matches the model well. Typically, the correlation search tool fails to realize that region 102 and 104 are part of the same object. Thus, the search tool often misses the ball 100 or, at the very least, generates a low correlation score for the ball 100 (i.e., indicates a low probability that the feature in the image is circular).
Another known technique to find balls is blob analysis, where blob analysis is also commonly called region analysis. Blob analysis segments foreground objects from background objects by the grey values of the foreground and the background pixels in the image. As is known in the art, it is often difficult to choose a threshold grey value between the foreground and the background. Even when features image well, a good threshold grey value can segment extraneous features. Choosing the correct threshold grey value is even more difficult for poor quality ball images. Consequently, blob analysis of poor quality ball images also often fails to segment enough balls to be useful in many applications.
Many applications can use the above techniques only if the application incorporates an expensive lighting system. The expensive lighting system can make the imaged balls appear roughly circular and/or annular, and, therefore, match well enough against the expected model, thereby making blob analysis useful. However, in some applications an expensive lighting system may not be desirable.
The invention provides methods and apparatuses for generating from an image a model of an object, where the object has similar features. The invention finds the similar features in the image by searching portions of the image for features that are substantially similar to a feature prototype.
The feature prototype is generated using candidate features within the image. Specifically, the candidate features are found in the image, feature profiles are generated therefrom, and the feature prototype is constructed using at least a subset of feature profiles. In one embodiment, the feature profiles are local images of balls of a ball grid array, and the feature prototype is an average of a sub-set of the local images of the balls.
One of the reasons the invention is robust is because the invention uses a feature prototype that is generated from the image to find the other features. Because the feature prototype is generated from the image, the feature prototype exhibits at least some of the same lighting effects as the features. Therefore, the lighting effects are less likely to frustrate the identification of the similar features. Thus, less expensive lighting systems can be employed.
In one embodiment, the subset of feature profiles creating the feature prototype are only the xe2x80x9cbestxe2x80x9d feature profiles. The xe2x80x9cbestxe2x80x9d feature profiles are ones representing the candidate features positioned near pattern-position points, where pattern-position points are given by a pattern that is generated as described below.
In one embodiment, a spatial pattern within the image is used to focus the search for similar features. More particularly, the search is conducted in neighborhoods of the image as directed by the pattern-position points of the spatial pattern. The spatial pattern is a pattern formed by a majority of the candidate features, and the pattern contains the pattern-position points. For instance, the pattern of an image of a ball grid array is the grid and specifics about the grid, while the pattern-positions are the intersections of the gridlines. The pattern is determined by: grouping at least a portion of the candidate balls into first sets of approximately collinear candidate balls, each of the first sets representing a first line, the first lines being substantially parallel to one another, grouping at least a portion of the candidate balls into second sets of approximately collinear candidate balls, each of the second sets representing a second line, the second lines being substantially parallel to one another and substantially orthogonal to the first lines; and determining the pattern formed by the first lines and the second lines. In one embodiment, the pattern includes the located gridlines and a patterned or uniform pitch or pitches between the located gridlines. The pattern can also include other information such as the origin and a grid angle of the located gridlines, where the grid angle is information that is implicit from the gridline.
One of the advantages of the invention is that it is less sensitive to poor lighting. Thus, an application of the invention remains robust while using less expensive lighting systems. The invention can also more easily find specularly reflecting features that image inconsistently. Further, the invention can identify features having aspects that are similar other than just one aspect, such as shape. Thus, the invention has uncanny accuracy, and therefore, the invention typically does not designate dissimilar features as similar.
In one embodiment, the geometrical model incorporates the spatial pattern, and the model can specify other aspects of the features, such as average size of the features, for example.
In further aspects, the invention can be used to find features of a specified-feature type in an image. Portions of the image are compared to the feature prototype to verify whether the portions of the image contain one of the features of the specified-feature type, such as a ball.
In further aspects, the invention provides an apparatus in accord with the methods described above. The aforementioned and other aspects of the invention are evident in the drawings and in the description that follows.